قضیه برژ
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
در نظریه گراف، قضیه برگه بیان میکند که یک تطابق (Matching) M از گراف G ماکسیمم است، اگر و تنها اگر مسیر M-افزوده(مسیری که یالهایش یکی در میان در تطابق باشد و همچنین اولین و آخرین یال هم جزء تطابق نباشد) نداشته باشیم. قضیه ایست که Claude Berge ریاضیدان فرانسوی در سال 1957 آن را به اثبات خود در آورد.
اثبات
[ویرایش]ابتدا به اثبات طرف اول رابطه بالا می پردازیم: از برهان خلف استفاده کرده و فرض می کنیم که مسیر M-افزوده داشته باشیم و تطابق ماکسیمم باشد. به سادگی میتوان گفت، در تطابق M از G با مسیر M-افزوده P، تطابق M` با تعداد یالهای بیشتر وجود خواهد داشت بهطوریکه (یالهایی که دقیقاً یک بار در یکی از M و P آمده اند)
اثبات عکس رابطه نیز بدین صورت است: فرض کنید M' یک تطابق بزرگتر از تطابق M) M-افزوده ندارد) است. در نتیجه را در نظر بگیرید. این گراف شامل راسهایی با حداکثر درجه 2 است. (چون هر راس در هر کدام از مچینگها حداکثر میتواند درجه 1 داشته باشد) در نتیجه گراف حاصل شامل یک سری دور با تعداد رئوس زوج و مسیر خواهد بود که یالها یکی در میان از M و M' هستند و همچنین تعداد یالهای M' از تعداد یالهای M بیشتر است. در دورهای زوج تعداد یالهایی که از M هستند با تعداد یالهای از M' برابر است، به علت آنکه این دو گراف دو تطابق میباشند تمامی مسیرها به گونهای است که یکی در میان یالهای آنها در M و M' حضور دارند. همان گونه که پیشتر گفته شد تعداد یالهای M' از تعداد یالهای M بیشتر است بنابراین در گراف جدید میتوان مسیری از رئوس پیدا کرد که طول آن در بیشترین حالت فرد باشد این مسیر برای گراف M یک مسیر بیشینه است و با فرض در تناقض است.
منابع
[ویرایش]کتاب مقدمهای بر نظریه گراف (نگارش دوم2)، نوشته دووگلاس بی وست.